home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Language/OS - Multiplatform Resource Library
/
LANGUAGE OS.iso
/
ast_comp
/
pfcthash.txt
< prev
next >
Wrap
Text File
|
1993-07-04
|
32KB
|
1,183 lines
#! /bin/sh
# This is a shell archive. Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file". To overwrite existing
# files, type "sh file -c". You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g.. If this archive is complete, you
# will see the following message at the end:
# "End of shell archive."
# Contents: perf.c
# Wrapped by oz@yunexus on Fri Dec 14 12:08:56 1990
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'perf.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'perf.c'\"
else
echo shar: Extracting \"'perf.c'\" \(29699 characters\)
sed "s/^X//" >'perf.c' <<'END_OF_FILE'
X
X/*
X * P e r f e c t H a s h
X *
X *
X * Program to search for Minimal Perfect Hash Functions for
X * use in lexical analyzers. C.D. Havener Jan 26 1982
X * GenRad Inc. 37 Great Road, Bolton Mass. 01740
X * Based on paper "Minimal Perfect Hash Functions Made Simple"
X * by Richard J. Cichelli - Comm. of ACM Jan 1980 pp 17-19
X *
X * Synopsis: The hash function is h = assoc value of 1st
X * letter + length of keyword + assoc value of last letter
X *
X * This program finds the associated values of the letters
X * given a list of keywords, 1 per line. It works most of
X * the time for up to about 40 keywords but certain
X * pathological cases exist. A semi-perfect hash is usually
X * found by the program. The user can then tighten the
X * default limits for max associated char value or the
X * table limit using the -v and -t options. Sometimes the
X * presort heuristics actually make the search process
X * much more difficult. The user can try his luck at manual
X * sorting using the -n option. Since the hash function
X * produces such a limited range of numbers it can only work
X * for up to about 40 keywords. If a language needs say 80
X * keywords just split them up into two tables and let the
X * lexical analyzer look in first one then the other, this
X * will still be much faster than any other keyword lookup.
X *
X * This program has run sucessfully on a VAX 11/780 under
X * 4.1BSD and VMS (using Vax-11 C and Decus C).
X */
X
X/*)BUILD
X $(MP) = 1 # uses macros with arguments
X $(STACK) = 10000 # lots of recursion
X $(TKBOPTIONS) = {
X STACK = 1024
X TASK = ...PRF
X }
X*/
X
X#ifdef DOCUMENTATION
Xtitle perfect Find Perfect Hash Functions
Xindex perfect Find perfect hash functions
X
Xsynopsis
X
X perfect [-options]
X
Xdescription
X
X perfect reads a list of keywords from the standard input
X and computes a "perfect hash" function for the set.
X The following options are defined:
X .lm +8
X .s.i -8;-d######Enable debug code.
X .s.i -8;-n######Disable pre-sort of keywords. (See below).
X .s.i -8;-t#<n>##Limit the maximum table size to <n> entries.
X .s.i -8;-v#<n>##Limit the maximum associated character value.
X .s.i -8;-k#<n>##Use only the first <n> keywords in the list.
X .s.i -8;-a#<n>##Give a status report every <n> seconds.
X (Unix and Vax-11C/VMS only).
X .s.i -8;-o#file#Write a sample keyword lookup routine to the
X indicated file.
X .s.lm -8
X The program prints a running commentary on the standard
X output.
X
XAuthor
X
X Charlie Havener, GenRad Inc. Bolton Mass.
X
X (Modified by Martin Minow, Dec, Maynard Mass.)
X
XDiscussion
X
X This technical note describes an implementation of a
X pragmatic algorithm for finding perfect or semi-perfect hash
X functions for lists of keywords. The resulting hash function can
X be used to speed up lexical analyzers used in translators and
X compilers. The algorithm was described by R.J. Cichelli in The
X January 1980 issue of Communications of the ACM under the title
X "Minimal Perfect Hash Functions made Simple." The article did not
X include a computer language description of the algorithm and some
X important implementation details were unclear. It is assumed that
X the user will know what to do with the output of this program.
X The -o option may be used to produce a lexical analyser kernel
X from the tables built by this program. Another reference for
X those wishing to pursue the topic further is "More On Minimal
X Perfect Hash tables" by Curtis Cook and R. Oldehoeft, a Colorado
X State University Technical Report.
X
X The program takes a list of keywords and sorts them in such
X a way that the search time for a hash function will be
X reasonable. Once sorted a recursive trial and error procedure
X hunts for a hash function satisfying user supplied bounds
X of table size and associated character value limits. The
X built-in hash function is
X
X hash = assoc value of first character
X + keyword length
X + assoc value of last character
X
X It is critically important to select a good ordering of the
X keywords before searching begins. I ran up 100 hours of VAX time
X searching for a hash function with an unordered list, and gave
X up. Once the sort heuristics were debugged it found the hash
X function in minutes. Typically it will find the function in
X minutes or you may as well give up. A status reporting feature is
X built into the program on the UNIX system that lets you follow
X the progress of the search depth. If it has trouble, you can
X tell just which word it can't get past, and take appropriate
X action. If it has trouble you can attempt to alter its choice of
X pre-ordering by moving troublesome words to the front of the
X list. In a sequel to his paper, Cichelli stated that sometimes
X the sort heuristics makes the search longer. There is also no
X guarantee that a hash function can be found. The program does the
X obvious precheck that no two keywords have the same first and
X last letter and length in common (e.g. BAK KAB). Nonetheless,
X as pointed out by Jaeschke and Osterberg in an overly harsh
X criticism, there are many pathological sets of keywords that fail.
X (On Cichelli's minimal perfect hash functions method. Comm. ACM
X Dec. 1980, pp 728-729) The algorithm also only works for up to
X about 40 keywords due to the limited range of numbers the formula
X can generate. If you have, say 80 keywords, just make two hash
X tables and look in each one. Here are some examples of the
X program's output:
X .s.nf
X Perfect hash function finder, CDH Ver. 2.9
X Start time = Mon Oct 17 20:40:40 1983
X 28 keywords, 19 distinct letters.
X The associated char value limit is 19
X The table size limit is 100
X The search ordering is
X else double continue case float struct sizeof
X static short extern typedef default register for
X char while entry int if return do unsigned switch
X union goto auto long break
X .s
X Success! Associated Char Values Follow:
X a =19, b = 4, c = 1, d = 0, e = 0, f = 3, g =17,
X h =14, i =17, k =19, l = 6, n = 8, o = 0, r =11,
X s = 6, t = 0, u =16, w =13, y =14,
X Hash min = 2, max = 30, spread = 29
X do 2, else 4, case 5, double 6, default 7,
X float 8, continue 9, typedef 10, short 11, struct 12,
X static 13, extern 14, sizeof 15, char 16, for 17,
X while 18, entry 19, int 20, goto 21, if 22, auto 23,
X unsigned 24, return 25, switch 26, long 27, break 28,
X union 29, register 30,
X .s
X Total search() invocations = 15913
X Started Mon Oct 17 20:40:40 1983
X Finished Mon Oct 17 20:40:42 1983
X .s.nf
X Perfect hash function finder, CDH Ver. 2.9
X Start time = Mon Oct 17 20:41:11 1983
X 39 keywords, 19 distinct letters.
X The associated char value limit is 19
X The table size limit is 100
X The search ordering is
X TEXT RESET TRUE REWRITE READLN SQRT SQR EOLN TRUNC
X PUT EXP PAGE CHR CHAR COS SUCC READ ROUND DISPOSE
X PRED SIN OUTPUT ORD INPUT INTEGER GET MAXINT REAL
X WRITE EOF FALSE NEW WRITELN LN ARCTAN ABS BOOLEAN
X PACK UNPACK
X .s
X Success! Associated Char Values Follow:
X A =18, B =11, C =16, D =18, E = 3, F = 3, G = 0,
X I = 1, K =19, L = 9, M =18, N =19, O = 8, P = 9,
X R = 0, S =14, T = 0, U =13, W =19,
X Hash min = 3, max = 45, spread = 43
X GET 3, TEXT 4, RESET 5, INPUT 6, TRUE 7,
X INTEGER 8, EOF 9, REWRITE 10, FALSE 11, PUT 12,
X REAL 13, OUTPUT 14, EXP 15, PAGE 16, SQR 17, SQRT 18,
X CHR 19, CHAR 20, TRUNC 21, READ 22, ROUND 23,
X MAXINT 24, READLN 25, EOLN 26, WRITE 27, DISPOSE 28,
X ORD 29, LN 30, PRED 31, PACK 32, COS 33, SUCC 34,
X ABS 35, SIN 36, BOOLEAN 37, UNPACK 38, NEW 41,
X ARCTAN 43, WRITELN 45,
X .s
X Total search() invocations = 149292
X Started Mon Oct 17 20:41:11 1983
X Finished Mon Oct 17 20:41:35 1983
X .s 2.f
X Usually, the first time you run perf, just let everything
X default. The second time,
X use the -t option to limit the table size to the first hash
X value plus the number of keywords.
X
X On Unix and Vax/VMS (Vax-11 C), The program will accept
X SIGTERM signals (CTRL/C on VMS) for an update status report
X since it may take quite a while to find the hash function values.
X
XSample keyword tables
X
X The following tables are known to work correctly.
X The first defines the keywords for the C programming
X language; the second for a toy computer language.
X
X int char float double struct union long short
X unsigned auto extern register typedef static
X goto return sizeof break continue if else for
X do while switch case default entry
X
X GET TEXT RESET OUTPUT MAXINT INPUT TRUE
X INTEGER EOF REWRITE FALSE CHR CHAR TRUNC REAL
X SQR SQRT WRITE PUT ORD READ ROUND READLN EXP
X PAGE EOLN COS SUCC DISPOSE NEW ABS LN BOOLEAN
X WRITELN SIN PACK UNPACK ARCTAN PRED
X
X#endif
X
X#include <stdio.h>
X#include <ctype.h>
X
X#define EOS '\0'
X#define FALSE 0
X#define TRUE 1
X#define VOID int
X
X#ifdef unix
X#define UNIX 1
X#define DOALARM 1
X#endif
X
X#ifndef vms
X#define VMS 0
X#else
X#define VMS 1
X#define DOALARM 1
X#endif
X
X#ifndef UNIX
X#define UNIX 0
X#endif
X
X#ifndef DOALARM
X#define DOALARM 0
X#endif
X
X#if UNIX
X#define IO_ERROR 1
X#endif
X
X#if VMS
X#include <ssdef.h>
X#define IO_ERROR SS$_ABORT
X/*
X * This creates text files in vanilla RMS on VMS
X */
Xextern FILE *fdopen();
X#define CREATE(f, m) fdopen(creat(f, 0, "rat=cr", "rfm=var"), m)
X#else
X#define CREATE fopen
X#endif
X
X#if DOALARM
X#include <signal.h>
Xextern int status();
X#endif
X
X#define MAXKEYS 100 /* Maximum number of keys */
X#define MAXCHARS 0377 /* Maximum number of char's */
X#define UNDEF -1 /* the undefined value */
X
Xtypedef struct keyword {
X int len; /* Keyword length */
X char last; /* Last byte of keyword */
X char word[1]; /* Keyword text */
X} KEYWORD;
X
X/*
X * Define some frequently used operations as macros:
X * hash(p) returns the hash value for this keyword
X * used(n) TRUE if this hash value is in use or illegal
X * defined(c) TRUE if this character is defined
X */
X
X#define hash(p) (value[p->word[0]] + p->len + value[p->last])
X#define used(n) ((n > tablesize || n < 0) ? TRUE : mapped[n])
X#define defined(c) (c != UNDEF)
X
Xchar cval[MAXCHARS]; /* All possible characters */
Xshort cused[MAXCHARS]; /* count of often char used */
Xshort order[MAXKEYS]; /* ordering of key words by subscript */
Xshort neworder[MAXKEYS]; /* the new supposedly improved ordering */
Xshort hashval[MAXKEYS]; /* current hashvalue of the key word */
Xshort value[MAXCHARS]; /* associated value of the character */
Xint mapped[MAXKEYS]; /* track which table entries are in use */
Xchar name[50]; /* bigger than any keyword should be */
X
X
XKEYWORD *keywds[MAXKEYS];
X
Xextern long time();
Xextern char *ctime();
Xextern char *malloc();
Xextern int aredefined();
Xextern char *strchr();
X
Xint debug = 0;
Xint nkeys = sizeof(keywds) / (sizeof (KEYWORD));
Xint tablesize = sizeof(keywds) / (sizeof (KEYWORD));
Xshort trys = 0;
Xint nletters = 0;
Xshort kilotrys = 0;
Xint atime = 10 * 60; /* default alarm status 10 min. */
Xchar *klimit = NULL;
Xchar *textp = NULL;
Xlong bigcount = 0;
Xshort depth = 0;
Xshort k_now = 0; /* value of k for status report */
Xint nosort = FALSE; /* -n sets nosort TRUE */
Xlong start, stop; /* the start and finish times */
Xshort vlimit = 0;
Xshort keylimit = 0;
Xshort tlimit = 0;
Xchar *output = NULL; /* Output file if set */
X
Xchar letters[37]; /* string of defined chars */
Xchar *letend = letters; /* -> free space in letters[] */
X
Xmain(argc,argv)
Xint argc;
Xchar *argv[];
X{
X getoptions(argc, argv);
X start = time(NULL);
X#if DOALARM
X signal(SIGALRM,status);
X signal(SIGTERM,status); /* status on kill -TERM pid */
X alarm(atime); /* status every N secs */
X#endif
X setup();
X dosort();
X printf("The search ordering is\n");
X prntorder();
X if (search(0)) {
X#if DOALARM
X alarm(0);
X#endif
X printf("\nSuccess! Associated Char Values Follow:\n");
X prntvals();
X prnthash();
X printf("\n");
X if (output != NULL)
X dooutput();
X }
X else {
X#if DOALARM
X alarm(0);
X#endif
X printf("\nFailed to find char values for hash function\n");
X }
X printf("Total search invocations = %ld, max depth = %d\n",
X bigcount, depth);
X stop = time(NULL);
X printf(" Started %s", ctime(&start));
X printf("Finished %s", ctime(&stop));
X}
X
Xsetup()
X{
X register KEYWORD *kp;
X register int c;
X register int i;
X int len;
X
X for (i = 0; (scanf("%s", name)) != EOF; i++) {
X if (i >= MAXKEYS) {
X printf("Too many keys, %d max.\n", MAXKEYS);
X exit(IO_ERROR);
X }
X len = strlen(name);
X kp = (KEYWORD *) malloc(sizeof (KEYWORD) + len);
X if (kp == NULL) {
X printf("Out of room allocating keywords\n");
X exit(IO_ERROR);
X }
X keywds[i] = kp;
X kp->len = len;
X kp->last = name[len - 1];
X strcpy(&kp->word[0], name);
X }
X nkeys = (keylimit == 0) ? i : keylimit;
X
X for (i = 0; i < MAXKEYS; i++) {
X hashval[i] = UNDEF;
X order[i] = i;
X mapped[i] = FALSE;
X }
X
X for (i = 0; i < MAXCHARS; i++) {
X cval[i] = 0;
X value[i] = UNDEF;
X }
X
X if (!precheck()) {
X printf("Perfect hash search terminated\n");
X exit(IO_ERROR);
X }
X
X for (i = 0; i < nkeys; i++) {
X c = keywds[i]->word[0]; /* Get first char of keyword */
X cval[c] = c; /* Remember this one used */
X if (cused[c] == 0) /* If it's the first time, */
X ++nletters; /* Count unique letters */
X ++cused[c]; /* count how often letter used */
X c = keywds[i]->last; /* Get last char of keyword */
X cval[c] = c; /* And do the same for it */
X if (cused[c] == 0)
X ++nletters;
X ++cused[c];
X }
X
X tablesize = (tlimit == 0 ? MAXKEYS : tlimit);
X printf("Perfect hash function finder, CDH Ver. 2.9\n");
X printf("Start time = %s", ctime(&start));
X printf("%d keywords, %d distinct letters.\n",
X nkeys, nletters);
X nletters = (vlimit > 0) ? vlimit : nletters;
X printf("The associated char value limit is %d\n", nletters);
X printf("The table size limit is %d\n", tablesize);
X
X /*
X * You should make tablesize at least nkeys + 1 since the
X * first value is usually 1 or 2 even if both assoc char
X * values are zero since the keyword length is included!
X */
X}
X
Xdosort()
X{
X register KEYWORD *kp;
X register int i, j;
X int k, m;
X int newvalues;
X
X if (nosort) {
X printf("No presorting of keywords.\n");
X return;
X }
X
X /*
X * first order by sum of frequencies of occurrences of each
X * keys 1st and last letter
X */
X
X for (i = 0; i < nkeys; i++) {
X kp = keywds[i];
X order[i] = cused[kp->word[0]] + cused[kp->last];
X }
X for (m = 0; m < nkeys; m++) {
X for (k = -1, i = 0; i < nkeys; i++) {
X if (order[i] > k) {
X k = order[i];
X j = i; /* remember keywd subscript */
X }
X }
X order[j] = 0;
X neworder[m] = j;
X }
X for (i=0; i < nkeys; i++)
X order[i] = neworder[i];
X if (debug > 2) {
X printf("After first ordering\n");
X prntorder();
X }
X
X /*
X * The second ordering follows, keywds whose values are
X * defined by keywds earlier in the order are placed
X * immediately after they are defined. This causes hash
X * value conflicts to occur as early during the search
X * as possible.
X */
X
X letend = letters;
X letters[0] = EOS;
X merge(order[0]); /* prime the pump */
X neworder[0] = order[0];
X order[0] = UNDEF;
X for (i = 1; i < nkeys;) {
X for (newvalues = TRUE; newvalues;) {
X newvalues = FALSE;
X for (k = 0; k < nkeys; k++) {
X if (order[k] == UNDEF)
X continue;
X if (aredefined(order[k])) {
X neworder[i++] = order[k];
X order[k] = UNDEF;
X continue;
X }
X }
X for (k = 0; k < nkeys; k++) {
X if (order[k] != UNDEF) {
X neworder[i++] = order[k];
X merge(order[k]);
X order[k] = UNDEF;
X newvalues = TRUE;
X break;
X }
X }
X }
X }
X for (i = 0; i < nkeys; i++)
X order[i] = neworder[i];
X if (precheck() == FALSE) {
X printf("OOPS - call a Guru, the presort botched it\n");
X prntorder();
X exit(IO_ERROR);
X }
X}
X
X/*
X * merge - adds keywd letters to the string of those defined.
X * This could be speeded up, but it's not a critical-path function.
X */
X
XVOID
Xmerge(n)
Xint n;
X{
X register KEYWORD *kp;
X
X kp = keywds[n];
X if (debug > 2)
X printf("merging in %s\n", kp->word);
X if (strchr(letters, kp->word[0]) == NULL) {
X *letend++ = kp->word[0];
X *letend = EOS;
X }
X if (strchr(letters, kp->last) != NULL) {
X *letend++ = kp->last;
X *letend = EOS;
X }
X}
X
X/*
X * aredefined - see if 1st & last char of keywd are defined
X */
X
Xint
Xaredefined(n)
Xint n;
X{
X register KEYWORD *kp;
X
X kp = keywds[n];
X if (strchr(letters, kp->word[0]) != NULL
X && strchr(letters, kp->last) != NULL)
X return (TRUE);
X else return (FALSE);
X}
X
X/*
X * precheck - all keywds length,1st and last char disjoint
X */
X
Xint
Xprecheck()
X{
X int pretest;
X register KEYWORD *ip, *jp;
X short i, j;
X short m, k;
X char a, b;
X
X pretest = TRUE;
X for (m = 0; m < nkeys; m++) {
X i = order[m];
X ip = keywds[i];
X a = ip->word[0];
X b = ip->last;
X for (k = m + 1; k < nkeys-1; k++) {
X j = order[k];
X jp = keywds[j];
X if (ip->len == jp->len
X && ((a == jp->word[0] && b == jp->last)
X || (a == jp->last && b == jp->word[0]))) {
X pretest = FALSE;
X printf("Precheck fails on %s and %s\n",
X ip->word, jp->word);
X }
X }
X }
X return (pretest);
X}
X
X/*
X * prntorder - printout the current order of the keywords
X */
X
XVOID
Xprntorder()
X{
X register int i, j;
X
X for (i = 0, j = 0; i < nkeys; i++) {
X if ((j + keywds[order[i]]->len) >= 60) {
X printf("\n");
X j = 0;
X }
X printf(" %s", keywds[order[i]]->word);
X j += keywds[order[i]]->len + 1;
X }
X printf("\n");
X}
X
X/*
X * prntvals - prints out the letter associated values
X */
X
Xprntvals()
X{
X register int i, j;
X
X for (i = 0, j = 0; i < MAXCHARS; i++) {
X if (cval[i]) {
X printf("%s %c =%2d,",
X ((++j % 10) == 0) ? "\n" : "",
X cval[i], value[i]);
X }
X }
X printf("\n");
X}
X
X/*
X * prnthash - prints out the hash values for the keywds
X */
X
XVOID
Xprnthash()
X{
X register int i, j;
X register KEYWORD *kp;
X int swap;
X int hmin;
X int hmax;
X int spread;
X
X
X swap = TRUE;
X hmin = MAXKEYS;
X hmax = 0;
X spread = 0;
X for (i = 0; i < nkeys; i++) {
X j = hashval[i] = hash(keywds[i]);
X hmin = (hmin < j) ? hmin : j;
X hmax = (hmax > j) ? hmax : j;
X order[i] = i;
X }
X while (swap) { /* plain vanilla bubble sort */
X swap = FALSE;
X for (i = 0; i < nkeys-1; i++) {
X if (hashval[order[i+1]] < hashval[order[i]]) {
X swap = TRUE;
X j = order[i];
X order[i] = order[i+1];
X order[i+1] = j;
X }
X }
X }
X printf("Hash min = %d, max = %d, spread = %d\n",
X hmin, hmax, hmax - hmin + 1);
X for (i=0, j=0; i < nkeys; i++, j++) {
X kp = keywds[order[i]];
X if (j + (kp->len + 5) > 60) {
X printf("\n");
X j = 0;
X }
X printf(" %s %d,", kp->word,
X hash(keywds[order[i]]));
X j += (kp->len + 5);
X }
X printf("\n");
X}
X
X/*
X * search - calls itself recursively to find char values
X */
X
Xint
Xsearch(k)
Xregister int k;
X{
X register KEYWORD *p;
X register int j;
X int m;
X short v1, v2, num;
X short sub1, sub2, subn;
X int thesame;
X
X thesame = FALSE;
X bigcount++;
X k_now = k; /* global for status reporting */
X if (k >= nkeys) /* hey - we may be all done */
X return (TRUE);
X if (k > depth) /* global for status reporting */
X depth = k; /* keep track of search depth */
X m = order[k];
X p = keywds[m];
X sub1 = p->word[0]; /* sub1 = first letter in word */
X sub2 = p->last; /* sub2 = last letter in word */
X if (sub1 == sub2)
X thesame = TRUE;
X v1 = value[sub1];
X v2 = value[sub2];
X if (defined(v1) && defined(v2)) {
X num = hash(p); /* Both letters defined */
X if (used(num))
X return (FALSE); /* this hash value is in use */
X else {
X hashval[m] = num; /* install it */
X mapped[num] = TRUE;
X if (search(k + 1))
X return (TRUE);
X else {
X hashval[m] = UNDEF;
X mapped[num] = FALSE;
X return (FALSE);
X }
X }
X }
X else if (defined(v1)) {
X for (j = 0; j <= nletters; j++) {
X v2 = j;
X num = v1 + p->len + v2;
X if (!used(num)) {
X hashval[m] = num;
X mapped[num] = TRUE;
X value[sub2] = v2;
X subn = sub2;
X if (search(k + 1))
X return (TRUE);
X else
X remove(m, sub2);
X }
X }
X return (FALSE);
X }
X else if (defined(v2)) {
X for (j = 0; j <= nletters; j++) {
X v1 = j;
X num = v1 + p->len + v2;
X if (!used(num)) {
X hashval[m] = num;
X mapped[num] =TRUE;
X value[sub1] = v1;
X subn = sub1;
X if (search(k + 1))
X return (TRUE);
X else
X remove(m, sub1);
X }
X }
X return (FALSE);
X }
X else { /* neither defined */
X for (j = 0; j <= nletters; j++) {
X if (thesame) {
X v1 = v2 = j;
X num = v1 + p->len + v2;
X if (!used(num)) {
X hashval[m] = num;
X mapped[num] = TRUE;
X value[sub1] = v1; /* same as value[sub2] */
X subn = sub1;
X if (search(k + 1))
X return (TRUE);
X else
X remove(m, subn);
X }
X }
X else {
X value[sub1] = j;
X if (search(k)) /* if never TRUE thru */
X return (TRUE); /* for loop, then FALSE */
X else
X value[sub1] = UNDEF;
X }
X }
X return (FALSE);
X }
X}
X
X/*
X * remove - backup by deleting keywds hash value etc
X */
X
XVOID
Xremove(m, subn)
Xregister short m;
Xregister short subn;
X{
X if (debug > 6)
X printf("removing %s, subn = %d\n", keywds[m]->word, subn);
X mapped[hashval[m]] = FALSE;
X hashval[m] = UNDEF;
X value[subn] = UNDEF;
X}
X
X/*
X * dooutput writes parser tables to the indicated output file.
X */
X
Xchar *function[] = {
X "",
X "int",
X "keyword(text)",
X "register char\t*text;",
X "/*",
X " * Look for keyword (string of alpha) in the perfect hash table",
X " * Return the index (L_xxx value) or 0 if not found",
X " */",
X "{",
X "\tregister char\t*tp;",
X "\tregister int\thash;",
X "",
X "\tif (*text < FIRST || *text > LAST)",
X "\t return (0);",
X "\tfor (tp = text; isalpha(*tp); tp++)",
X "\t ;",
X "\thash = (tp - text);",
X "\tif (*--tp < FIRST || *tp > LAST)",
X "\t return (0);",
X "\thash += (px_assoc - FIRST)[*text] + (px_assoc - FIRST)[*tp];",
X "\tif (px_table[hash] == NULL)",
X "\t return (0);",
X "\tif (strncmp(text, px_table[hash], (tp - text + 1)) != 0)",
X "\t return (0);",
X "\treturn(hash);",
X "}",
X "",
X NULL,
X};
X
Xdooutput()
X{
X FILE *fd;
X register char **funp;
X register int i;
X int first, last, hval;
X
X if ((fd = CREATE(output, "w")) == NULL) {
X perror(output);
X return;
X }
X fprintf(fd, "#include <stdio.h>\n");
X fprintf(fd, "#include <ctype.h>\n");
X for (i = 0; i < nkeys; i++) {
X fprintf(fd, "#define\tL_%s\t", keywds[order[i]]->word);
X if (keywds[order[i]]->len < 14)
X putc('\t', fd);
X if (keywds[order[i]]->len < 6)
X putc('\t', fd);
X fprintf(fd, "%d\n", hash(keywds[order[i]]));
X }
X for (i = MAXCHARS; --i >= 0 && cval[i] == 0;)
X ;
X last = i;
X for (i = 0; i <= last && cval[i] == 0;)
X i++;
X first = i;
X fprintf(fd, "#define FIRST\t'%c'\n", first);
X fprintf(fd, "#define LAST\t'%c'\n", last);
X fprintf(fd, "static char px_assoc[] = {\n");
X while (i <= last) {
X fprintf(fd, "\t%d,\t/* '%c' */\n", value[i], i);
X i++;
X }
X fprintf(fd, "};\n");
X fprintf(fd, "static char *px_table[] = {\n");
X last = 0;
X for (i = 0; i < nkeys; i++) {
X hval = hash(keywds[order[i]]);
X while (last < hval) {
X fprintf(fd, "\tNULL,\t\t\t/*%3d\t*/\n", last);
X last++;
X }
X fprintf(fd, "\t\"%s\",\t", keywds[order[i]]->word);
X if (keywds[order[i]]->len < 13)
X putc('\t', fd);
X if (keywds[order[i]]->len < 5)
X putc('\t', fd);
X fprintf(fd, "/*%3d\t*/\n", hval);
X last = hval + 1;
X }
X fprintf(fd, "};\n");
X for (funp = function; *funp != NULL; funp++)
X fprintf(fd, "%s\n", *funp);
X fclose(fd);
X}
X
X#if DOALARM
X/*
X * status - on signal this reports the current statistics
X */
X
XVOID
Xstatus()
X{
X fprintf(stderr,
X "\nSTATUS: key \"%s\" (%d), search calls = %ld, max depth = %d\n",
X keywds[k_now]->word, k_now, bigcount, depth);
X fflush(stderr);
X signal(SIGTERM,status);
X signal(SIGALRM,status);
X alarm(atime);
X}
X#endif
X
X/*
X * G E T O P T I O N S
X *
X * Generalized command line argument processor. The following
X * types of arguments are parsed:
X * flags The associated int global is incremented:
X * -f f-flag set to 1
X * -f123 f-flag set to 123 (no separator)
X * -fg f-flag and g-flag incremented.
X * values A value must be present. The associated
X * int global receives the value:
X * -v123 value set to 123
X * -v 123 value set to 123
X * arguments The associated global (a char *) is
X * set to the next argument:
X * -f foo argument set to "foo"
X */
X
X#define FLAG 0
X#define VALUE 1
X#define ARG 2
X#define ERROR 3
X
Xtypedef struct argstruct {
X char opt; /* Option byte */
X char type; /* FLAG/VALUE/ARG */
X char *name; /* What to set if option seen */
X char *what; /* String for error message */
X} ARGSTRUCT;
X
Xstatic ARGSTRUCT arginfo[] = {
X{ 'd', FLAG, (char *)&debug, "debug" },
X{ 'a', VALUE, (char *)&atime, "alarm time for status" },
X{ 't', VALUE, (char *)&tlimit, "table size limit" },
X{ 'v', VALUE, (char *)&vlimit, "associated value limit" },
X{ 'k', VALUE, (char *)&keylimit, "keyword limit" },
X{ 'n', FLAG, (char *)&nosort, "no sort wanted" },
X{ 'o', ARG, (char *)&output, "parser output file" },
X{ EOS, ERROR, NULL, NULL },
X};
X
Xstatic char *argtype[] = {
X "flag", "takes value", "takes argument"
X};
X
Xstatic
Xgetoptions(argc, argv)
Xint argc;
Xchar **argv;
X/*
X * Process arg's
X */
X{
X register char *ap;
X register int c;
X register ARGSTRUCT *sp;
X int i;
X int helpneeded;
X
X getredirection(argc, argv);
X helpneeded = FALSE;
X for (i = 1; i < argc; i++) {
X if ((ap = argv[i]) != NULL && *ap == '-') {
X argv[i] = NULL;
X for (ap++; (c = *ap++) != EOS;) {
X if (isupper(c))
X c = tolower(c);
X sp = arginfo;
X while (sp->opt != EOS && sp->opt != c)
X sp++;
X switch (sp->type) {
X case FLAG: /* Set the flag */
X if (!isdigit(*ap)) {
X (*((int *)sp->name))++;
X break;
X }
X case VALUE: /* -x123 */
X if (isdigit(*ap)) {
X *((int *)sp->name) = atoi(ap);
X *ap = EOS;
X }
X else if (*ap == EOS && ++i < argc) {
X *((int *)sp->name) = atoi(argv[i]);
X argv[i] = NULL;
X }
X else {
X fprintf(stderr,
X "Bad option '%c%s' (%s)",
X c, ap, sp->what);
X fprintf(stderr, ", ignored\n");
X helpneeded++;
X }
X break;
X
X case ARG: /* -x foo */
X if (++i < argc) {
X *((char **) sp->name) = argv[i];
X argv[i] = NULL;
X }
X else {
X fprintf(stderr,
X "Argument needed for '%c' (%s)",
X c, sp->what);
X fprintf(stderr, ", ignored\n");
X helpneeded++;
X }
X break;
X
X case ERROR:
X fprintf(stderr,
X "Unknown option '%c', ignored\n", c);
X helpneeded++;
X break;
X }
X }
X }
X }
X if (helpneeded > 0) {
X for (sp = arginfo; sp->opt != EOS; sp++) {
X fprintf(stderr, "'%c' -- %s (%s)\n",
X sp->opt, sp->what, argtype[sp->type]);
X }
X }
X}
X
X/*
X * getredirection() is intended to aid in porting C programs
X * to VMS (Vax-11 C) which does not support '>' and '<'
X * I/O redirection. With suitable modification, it may
X * useful for other portability problems as well.
X */
X
X#include <stdio.h>
X
Xgetredirection(argc, argv)
Xint argc;
Xchar **argv;
X/*
X * Process vms redirection arg's. Exit if any error is seen.
X * If getredirection() processes an argument, argv[i], it is changed
X * to NULL.
X *
X * Warning: do not try to simplify the code for vms. The code
X * presupposes that getredirection() is called before any data is
X * read from stdin or written to stdout.
X *
X * Normal usage is as follows:
X *
X * main(argc, argv)
X * int argc;
X * char *argv[];
X * {
X * register int i;
X * int nargs;
X *
X * getredirection(argc, argv); ** setup redirection
X * for (nargs = 0, i = 1; i < argc, i++) {
X * if (argv[i] == NULL) ** skip if processed
X * continue; ** by getredirection()
X * nargs++; ** here is an argument
X * ... ** process argv[i]
X * }
X * if (nargs == 0) { ** no arguments given
X * ...
X * }
X * }
X */
X{
X#ifdef vms
X register char *ap; /* Argument pointer */
X int i; /* argv[] index */
X int file; /* File_descriptor */
X extern int errno; /* Last vms i/o error */
X
X for (i = 1; i < argc; i++) { /* Do all arguments */
X if (*(ap = argv[i]) == '<') { /* <file */
X if (freopen(++ap, "r", stdin) == NULL) {
X perror(ap); /* Can't find file */
X exit(errno); /* Is a fatal error */
X }
X goto erase_arg; /* Ok, erase argument */
X }
X else if (*ap++ == '>') { /* >file or >>file */
X if (*ap == '>') { /* >>file */
X /*
X * If the file exists, and is writable by us,
X * call freopen to append to the file (using the
X * file's current attributes). Otherwise, create
X * a new file with "vanilla" attributes as if
X * the argument was given as ">filename".
X * access(name, 2) is TRUE if we can write on
X * the specified file.
X */
X if (access(++ap, 2) == 0) {
X if (freopen(ap, "a", stdout) == NULL) {
X perror(ap);
X exit(errno);
X }
X else goto erase_arg;
X } /* If file accessable */
X else ; /* Else it's just >file */
X }
X /*
X * On vms, we want to create the file using "standard"
X * record attributes. create(...) creates the file
X * using the caller's default protection mask and
X * "variable length, implied carriage return"
X * attributes. dup2() associates the file with stdout.
X */
X if ((file = creat(ap, 0, "rat=cr", "rfm=var")) == -1
X || dup2(file, fileno(stdout)) == -1) {
X perror(ap); /* Can't create file */
X exit(errno); /* is a fatal error */
X } /* If '>' creation */
Xerase_arg: argv[i] = NULL; /* red. erases argument */
X } /* If redirection */
X } /* For all arguments */
X#endif
X#ifdef decus
X argc = argv[0]; /* Supress warning msg. */
X#endif
X}
X
X#if UNIX
X/*
X * The following is missing on some Unix systems
X */
X
Xchar *
Xstrchr(string, c)
Xregister char *string;
Xregister char c;
X/*
X * If 'c' is in string, return a pointer to it.
X * Else, return NULL.
X */
X{
X do {
X if (*string == c)
X return (string);
X } while (*string++ != EOS);
X return (NULL);
X}
X#endif
END_OF_FILE
if test 29699 -ne `wc -c <'perf.c'`; then
echo shar: \"'perf.c'\" unpacked with wrong size!
fi
# end of 'perf.c'
fi
echo shar: End of shell archive.
exit 0
